#!/usr/bin/env python3
# coding: utf-8


def mergesort(array, l=0, r=-1):
    if r == -1:
        r = len(array)
    if len(array) > 1:
        mergesort(array[:len(array) // 2])
        mergesort(array[len(array) // 2:])
        array = merge(array)
    return array

def merge(array):
    sorted = [None] * len(array)
    s = 0
    l = 0
    r = len(array) // 2
    while l < len(array) // 2 and r < len(array):
        if array[l] < array[r]:
            sorted[s] = array[l]
            l += 1
        else:
            sorted[s] = array[r]
            r += 1
        s += 1
    #print('array={}, sorted={}, s={}'.format(array, sorted, s))
    while l < len(array) // 2:
        sorted[s] = array[l]
        l += 1
        s += 1
        #print('array={}, sorted={}, s={}'.format(array, sorted, s))
    while r < len(array):
        sorted[s] = array[r]
        r += 1
        s += 1
        #print('array={}, sorted={}, s={}'.format(array, sorted, s))
    assert s == len(array) == len(sorted)
    print(sorted)
    return sorted

def pr():
    pass
